//哈希表
//将数组所有的数放入哈希表中
//再检查[1, N]的数是否在哈希表中，第一个不在的就是结果
//如果都在，结果就是N+1
// class Solution {
// public:
//     int firstMissingPositive(vector<int>& nums) {
//         unordered_set<int> hash;

//         for (auto i : nums)
//             hash.insert(i);
            

//         for (int i = 1;; i++)
//         {
//             if (!hash.count(i))
//                 return i;
//         }

//         return nums.size() + 1;
//     }
// };

//将原数组看成哈希表
//将数组中的每个正数nums[i]放在下标为nums[i] - 1上
//放完后，遍历数组，第一个不符合 num[i] = i + 1 的位置就是结果
//结果即i+1
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; i++)
        {
            //i位置
            //1. 如果为非正数, 2. 如果nums[i] >= len
            //3. 如果nums[i]已经在正确位置（nums[i] == i + 1)
            //4. 如果要被交换的数重复（nums[nums[i] - 1] == nums[i]）
                //4.1 如果能走到这个条件，就说明nums[i]在数组中一定有位置可以放，但是他的位置被前面重复的元素占用了
                //4.2 如果不写这一条件，就会死循环
                //4.2 条件3已经被包含在了条件4中
            //那么就不需要交换
            //交换完后，并不知道位置i的元素是否仍满足要求，因此还需要继续交换
            //所以要使用while而不是if
            while (nums[i] > 0 && nums[i] < len && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        }

        for (int i = 0; i < len; i++)
            if (nums[i] != i + 1)
                return i + 1;
        return len + 1;
    }
};